/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 void flatHelper(TreeNode *root, TreeNode *&start, TreeNode *&end)
{
    if (!root) {
        return;
    }   

    if (!root->left && !root->right) {start = root; end = root; return;}
    TreeNode *leftStart = NULL, *leftEnd = NULL, *rightStart = NULL, *rightEnd = NULL;
    flatHelper(root->left, leftStart, leftEnd);    
    flatHelper(root->right, rightStart, rightEnd);    
    root->left = NULL;
    root->right = leftStart;
    if (leftStart) leftStart->left = root;
    if (leftEnd) leftEnd->right = rightStart;
    if (rightStart) rightStart->left = leftEnd;
    start = root;
    if (rightStart) end = rightEnd;
    else end = leftEnd;
}

class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      TreeNode *start = NULL, *end = NULL;
    flatHelper(root, start, end);      
    }
};
